package tree;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName RedBlackTree.java
 * @Description TODO
 * @createTime 2020年08月18日 10:01:00
 */
public class RedBlackTree<E extends TreeComparable> extends BaseBalanceTree<E >{
	private static final boolean RED=false;
	private static final boolean BLACK=true;

	public RedBlackTree() {
		this(null);
	}

	public RedBlackTree(TreeComparable<E> comparable) {
		super(comparable);
	}
	private static class RedBlackTreeNode<E extends TreeComparable> extends Node<E> {
		boolean color=RED;

		public RedBlackTreeNode(E element, Node<E> parent) {
			super(element, parent);
		}
	}

	@Override
	protected Node<E> createNode(E element, Node<E> parent) {
		return new RedBlackTreeNode<>(element,parent);
	}

	private Node<E> color(Node<E> node, boolean color){
		if (node!=null){
			((RedBlackTreeNode<E>)node).color=color;
			return node;
		}else {
			return null;
		}
	}

	private Node<E> red(Node<E> node){
		return color(node,RED);
	}

	private Node<E> black(Node<E> node){
		return color(node,BLACK);
	}

	private boolean colorOf(Node<E> node){
		if (node!=null){
			return ((RedBlackTreeNode<E>)node).color;
		}else {
			return BLACK;
		}
	}

	private boolean isBlack(Node<E> node){
		return colorOf(node)==BLACK;
	}
	private boolean isRed(Node<E> node){
		return colorOf(node)==RED;
	}
	@Override
	protected void balanceTree(Node<E> node) {
		//父节点为黑色，直接添加
		Node<E> parent=node.parent;
		//添加的节点为根节点或上溢为根节点
		if (parent==null){
			black(node);
			return;
		}
		if (isBlack(parent)){
			return;
		}
		//叔父节点
		Node<E> uncle=parent.sibling();
		//祖父节点
		Node<E> grand=parent.parent;
		//叔父节点为红色，grand到添加节点顺序为RR、LL，RL，LR ,则：1. parent染成黑色，grand 染成 黑色，2：grand相当合并（相当于新添加grand节点）
		if (isRed(uncle)){//叔父节点是红色，相当于上溢的处理
			black(uncle);
			black(grand);
			//祖父节点当做新添加节点
			balanceTree(red(grand));
			return;
		}
		//叔父节点为黑色，grand到添加节点顺序为RR、LL，RL，LR，
		if (parent.isLeftChild()){
			red(grand);
			if (node.isLeftChild()){//LL parent染成黑色，grand染成红色，grand进行右旋
				black(parent);
			}else {//LR
				black(node);
				rotateLeft(parent);
			}
			rotateRight(grand);
		}else {
			red(grand);
			if (node.isLeftChild()){//RL
				black(node);
				rotateRight(parent);
			}else {//RR parent染成黑色，grand染成红色，grand进行右旋
				black(parent);
			}
			rotateLeft(grand);
		}
	}

	@Override
	protected void afterRemove(Node<E> node,Node<E> replacement) {
		//如果删除的节点是红色直接返回
		if (isRed(node)) {
			return;
		}
		//用以取代node的子节点是红色
		if (isRed(replacement)){
			black(replacement);
			return;
		}
		//删除的是根节点
		Node<E> parent = node.parent;
		if (parent==null){
			return;
		}
		//删除是黑色叶子节点。
		//判断被删除的node是左还是右
		boolean left = parent.left == null || node.isLeftChild();
		Node<E> sibling = left ? parent.right : parent.left;
		if (left){
			if (isRed(sibling)){//兄弟节点是红色
				black(sibling);
				red(parent);
				rotateLeft(parent);
				//更换兄弟
				sibling=parent.right;
			}
			//兄弟节点是黑色
			if (isBlack(sibling.left)&&isBlack(sibling.right)){//兄弟节点没有1个是红色节点
				boolean parentBlcak=isBlack(parent);//父节点也是黑色的则父节点下溢，只需要吧父节点仿作被删除的节点处理
				black(parent);
				red(sibling);
				if (parentBlcak){
					afterRemove(parent,null);
				}
			}else {//兄弟节点至少有一个红色子节点，向兄弟节点借
				if (isBlack(sibling.right)){//兄弟节点的左边是黑色,就是LR的情况，先旋转兄弟，然后旋转父节点
					rotateRight(sibling);
					sibling=parent.right;
				}
				color(sibling,colorOf(parent));//
				black(sibling.right);
				black(parent);
				rotateLeft(parent);
			}
		}else {
			if (isRed(sibling)) { // 兄弟节点是红色
				black(sibling);
				red(parent);
				rotateRight(parent);
				// 更换兄弟
				sibling = parent.left;
			}

			// 兄弟节点必然是黑色
			if (isBlack(sibling.left) && isBlack(sibling.right)) {
				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并
				boolean parentBlack = isBlack(parent);
				black(parent);
				red(sibling);
				if (parentBlack) {
					afterRemove(parent,null);
				}
			} else { // 兄弟节点至少有1个红色子节点，向兄弟节点借元素
				// 兄弟节点的左边是黑色，兄弟要先旋转
				if (isBlack(sibling.left)) {
					rotateLeft(sibling);
					sibling = parent.left;
				}

				color(sibling, colorOf(parent));
				black(sibling.left);
				black(parent);
				rotateRight(parent);
			}
		}
		//删除的节点的兄弟节点是黑色
	}


}
